import os
import sys

# 请在此输入您的代码
tree_sum = [0] * (10 ** 6)
# 维护区间最大值，因为一个树最多开log次根号，可以暴力处理
tree_max = [0] * (10 ** 6)


def push_up(o, l, r):
    if l == r:
        return
        # 更新值
    lson, rson = o * 2, o * 2 + 1
    tree_sum[o] = tree_sum[lson] + tree_sum[rson]
    tree_max[o] = max(tree_max[lson], tree_max[rson])


# 1.建树
def build(o, l, r):
    # 结束条件
    if l == r:
        tree_sum[o] = a[l]
        tree_max[o] = a[l]
        return

    mid = (l + r) // 2
    lson = o * 2
    rson = o * 2 + 1
    build(lson, l, mid)
    build(rson, mid + 1, r)
    # 回溯 ,向上更新值
    push_up(o, l, r)


# 区间 根号， 暴力处理
def updata_sqrt(o, l, r, L, R):
    # 当前节点最大值不超过1，不需要进行 开根号
    if tree_max[o] <= 1:
        return

    # 暴力开根号，直接 遍历到对应的叶子节点
    if l == r:
        tree_sum[o] = tree_max[o] = int(tree_sum[o] ** 0.5)
        return

    mid = (l + r) // 2
    lson = o * 2
    rson = o * 2 + 1
    if mid >= L:
        updata_sqrt(lson, l, mid, L, R)
    if mid + 1 <= R:
        updata_sqrt(rson, mid + 1, r, L, R)

    # 回溯
    push_up(o, l, r)


# 区间查询
def query(o, l, r, L, R):
    # 结束条件
    if L <= l <= r <= R:
        return tree_sum[o]
    mid = (l + r) // 2
    lson = o * 2
    rson = o * 2 + 1
    res = 0
    if mid >= L:
        # 结果累加
        res += query(lson, l, mid, L, R)
    if mid + 1 <= R:
        res += query(rson, mid + 1, r, L, R)

    push_up(o, l, r)
    return res


n, q = map(int, input().split())
a = [0] + list(map(int, input().split()))

build(1, 1, n)
for _ in range(q):
    now = list(map(int, input().split()))
    l, r = now[1::]
    if now[0] == 1:
        updata_sqrt(1, 1, n, l, r)
    else:
        print(query(1, 1, n, l, r))


